from random import randint
from copy import deepcopy

from algo.sort.fast import FastSort
from utils.profile import Profile
from utils.generator import Generator


class Nth(FastSort):
    def __init__(self, arr):
        super(Nth, self).__init__(arr)

    @Profile(end=True)
    def find(self, n, left=None, right=None):
        if n > self.len - 1:
            self.simple_error('index exceed')
        left = 0 if left is None else left
        right = self.len - 1 if right is None else right
        x = self.arr[randint(left, right)]
        first, last = self.partition_optimize(left, right, x)
        if first <= n <= last:
            return x
        if n < first:
            return self.find(n, left, first - 1)
        if n > last:
            return self.find(n, last + 1, right)


if __name__ == '__main__':
    arr = Generator().do()
    arr2 = deepcopy(arr)
    arr3 = deepcopy(arr)

    n = randint(0, len(arr) - 1)
    arr.sort()
    print(arr)
    print(arr[n])

    print(Nth(arr2).find(n))
    print(arr2)

    n = len(arr3) * 2
    print(Nth(arr3).find(n))
